import java.util.Scanner;

/**
 * @author tongchen
 * @create 2023-02-06 20:29
 */
public class ClimbStairs {
    /**
     * 数组反转找最小值：将升序数组反转之后找其中的最小值
     * @param arr
     * @return
     */
    public  static int reverse(int[]arr,int left ,int right){
        //正常情况下左边大于右边
        if(arr[left]<arr[right]){
            return left;
        }
        //当我们的范围界限内只剩下两个元素的时候，右边那个是最小值
        while(left+1<right){
            int mid=left+(right-left)/2;
            //排除特殊情况
            if(arr[left]==arr[mid]&&arr[mid]==arr[right]){
                //利用顺序遍历
                int min=arr[left];
                for(int i=left;i<=right;++i){
                    if(arr[i]<min){
                        min=i;
                    }
                }
                return min;
            }
            //正常情况向左向右遍历
            //当begin>mid，说明右边有序
            if(arr[left]>arr[mid]){
                right=mid;
            }
            else {
               left=mid;
            }
            //当begin<mid,说明左边有序



        }
        return right;
    }
    /**
     * 爬楼梯问题：递归的典型例题，当有n阶梯子时，我们有n-1 n-2 n-3这三阶梯子直接上去，同理这是重复，变化的是规模，当n=0 1 2 时是边界
     * @param n
     * @return
     */
    public static int climbStairs(int n){
        //边界问题
        if(n==0){
            return 1;
        }
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }

        return climbStairs(n-1)+climbStairs(n-2)+climbStairs(n-3);
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int[]arr={3,4,5,1,2};
        System.out.println(reverse(arr, 0, 4));

        //while(true){
           // int x=scanner.nextInt();
            //System.out.println(climbStairs(x));

       // }
    }
}
